"""
给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]

链接：https://leetcode-cn.com/problems/permutations
"""
from mode import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        if n == 0:
            return [[]]
        if n == 1:
            return [[nums[0]]]

        def dfs(x):
            if x == n:
                res.append(list(nums))
                return

            dic = set()

            for i in range(x, n):
                if nums[i] in dic:
                    continue

                dic.add(nums[i])
                nums[i], nums[x] = nums[x], nums[i]
                dfs(x + 1)
                nums[i], nums[x] = nums[x], nums[i]

        res = []
        dfs(0)
        return res


class Solution1:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []

        def dfs(x):
            if x == n and nums not in res:
                res.append(list(nums))

            for i in range(x, n):
                nums[i], nums[x] = nums[x], nums[i]
                dfs(x+1)
                nums[i], nums[x] = nums[x], nums[i]

        dfs(0)
        return res

if __name__ == "__main__":
    nums = [1, 1, 2]
    # A = Solution()
    # print(A.permute(nums))

    A = Solution1()
    print(A.permute(nums))
